#ifndef ARBOL_B_H_
#define ARBOL_B_H_

/**********************************************************************
 * arbol_b.h
 * 
 * Descripcion: Esta clase representa un arbol B en disco, que almacena
 * informacion en los nodos del tipo [clave, unsigned int].
*********************************************************************/

#include "tipo_dato.h"
#include "tipo_int.h"
#include "arch_bloques_libres.h"
#include "nodo.h"
#include "debugger.h"
#include <limits.h>
#include <assert.h>

//DEFINICIONES
#define _NODO_RAIZ_			1 //en el 0 guardo el header
#define _EXT_BBLL_			".bl"
#define _TAM_BBLL_			128
#define _PORCENTAJE_MIN_	0.5  
 

class ArbolB : public Archivo {

	protected:
	
		ArchBloquesLibres * bloques_libres;
		
		TipoDato * base;
		TipoDato * base_hoja;
		TipoDato * base_interno;
		
		/*
		 * Metodos para escribir y leer desde el header la cantidad de 
		 * bloques
		 */ 
		void escribir_cant_bloques(unsigned int cant);
		unsigned int leer_cant_bloques();
	
		/*
		 * Estructura auxiliar para las busquedas, consultas y eliminaciones
		 */ 
		struct tElemNodo{
			TipoDato * clave;
			TipoInt  * dato;
			unsigned short int der;
			unsigned short int izq;
		};
		typedef struct tElemNodo ElemNodo;
				
			
	public:
	
		ArbolB(std::string nombre, unsigned int tam_bloque);
	
		virtual ~ArbolB();
		
		virtual void crear() throw(ExcepCreandoArch);
	
		virtual void abrir() throw(ExcepAbriendoArch);
		
		virtual void eliminar();
		
		virtual void cerrar();
		
		/*
		 * Ingresa la clave junto con el dato en el nodo correspondiente.
		 */ 
		virtual void ingresar(TipoDato * clave, TipoInt * dato) throw(ExcepArchCerrado,ExcepErrorTipos, ExcepBloqueTam, ExcepRegExistente, ExcepLeerBloque);
		
		virtual bool quitar(TipoDato* clave) throw(ExcepArchCerrado,ExcepErrorTipos,  ExcepLeerBloque);
		
		/*
		 * Devuelve el contenido que se encuentra acompañando a la clave
		 * en el indice. En caso de no existir devuelve NULL
		 */
		virtual TipoInt * consultar(TipoDato * clave) throw(ExcepArchCerrado,ExcepLeerBloque);
		
		/*
		 * Devuelve el tamano ocupado por el archivo, en bytes
		 */ 
		virtual long get_tam() throw(ExcepArchCerrado);
 		 
		/*
		* Devuelve el espacio libre en bytes
		*/ 
		virtual unsigned int get_espacio_libre()  throw(ExcepArchCerrado, ExcepLeerBloque);
		
		virtual TiposArchivo get_tipo_archivo();

		/*
		 * Metodo para setearle el tipo base que utiliza para la clave
		 */ 
		virtual void set_tipo_base(TipoDato &base);
		
		/*
 		 * Devuelve la cantidad de registros en el archivo.
 		 */
 		unsigned int get_cant_regs() throw(ExcepArchCerrado);
 		
	
	protected:
		/*
 		 * Concatena nodos
 		 */ 
 		virtual void concatenar(Nodo * nodo, Nodo * hijo, bool hijo_derecho);
 		
 		/*
 		 * Redistribuye los elementos del nodo para que no queden en 
 		 * underflow. Primero intenta con el nodo de la izquierda, luego
 		 * con el de la derecha. Devuelve true si pudo hacerlo.
 		 */ 
 		virtual bool redistribuir( Nodo * nodo, Nodo * hijo, bool hijo_derecho );
 		
		/*
		 * Maneja el overflow para todos los nodos menos la raiz. Resuelve
		 * la propagacion sin llegar a esta.
		 */ 
		virtual bool manejar_overflow(Nodo * padre, Nodo * Hijo, ElemNodo * elem);
		
	
		/*
		 * Recibe un los valores a ingresar y el nodo raiz, se mueve
		 * recursivamente hasta insertarlo en una hoja. 
		 * Tiene en cuenta los casos de overflow.
		 * Guarda los bloques que sufrieron modificaciones
		 * Devuelve false si la raiz quedo con overflow
		 */
 		virtual bool ingresar_interno(ElemNodo * elem, Nodo * nodo);
 		
 		/*
		 * Metodo que en forma recursiva consulta por la existencia de un
		 * elemento. En retorno devuelve si lo encontro, false en caso 
		 * contrario
		 */ 
		virtual void consultar_interno(Nodo * nodo, TipoDato * clave, TipoInt ** retorno );
		
		/*
		 * En forma recursiva resuelve la eliminacion de un elemento en
		 * el arbol. Devuelve true si lo pudo quitar, false en caso contrario.
		 * Se encarga del manejo del underflow.
		 * Permite utilizar un puntero para pasaje de parametros auxiliares
		 */ 
		virtual bool quitar_interno(Nodo * nodo, TipoDato * clave, void **param = NULL);
		
		/*
		 * Crea un bloque nuevo y lo guarda en disco.
		 * Opcional: Pasarle el nivel que posee el nodo.
		 */ 
		virtual void crear_bloque(unsigned short int nivel = 0) throw(ExcepEscribirBloque);
		
		/*
		 * Devuelve el primer bloque libre que puede asignandole el nivel 
		 * pasado por parametro.
		 * Si no habia ninguno, lo crea.
		 */
		virtual Bloque * get_bloque_libre(unsigned short int nivel  = 0);
		
		
		/*
		 * Maneja el overflow producido sobre el nodo raiz. Crea dos nodos
		 * para esto
		 */ 
		virtual void overflow_en_raiz(Nodo * raiz, ElemNodo * elem);
		
				
		/*
 		 * Intercambia el elemento con clave pasada por param (que SE 
 		 * ENCUENTRA en el nodo) con el menor de los mayores. 
 		 * Acutaliza en disco los cambios realizados
 		 */ 
 		virtual void intercambiar_con_menor_mayores(Nodo * nodo, TipoDato * clave);		
 		
 		/*
 		 * Deuvelve true si el tamano ocupado en el bloque del nodo
 		 * es menor que un porcentaje del nodo vacio. Este param esta
 		 * regulado en _PORCENTAJE_MIN_
 		 */
 		virtual bool hay_underflow(Nodo * hijo);
 		
 		
 		/*
 		 * Maneja el underflow. Primero intenta redistribuir elementos
 		 * y si esto no se puede, concatena nodos.
 		 * Recibe el padre y el hijo que produjo el underflow. Tambien
 		 * si este ultimo era el hijo derecho o izquierdo.
 		 */ 
 		virtual void manejar_underflow( Nodo * nodo, Nodo * hijo, bool hijo_derecho );
 		
 		
 		/*
 		 * Le saca un elemento al vecino y al padre. Luego le inserta
 		 * el del vecino al padre y el del padre al hijo. 
 		 * Esto lo realiza si no queda en underflow el vecino.
 		 */ 
 		virtual bool prestar_elemento(Nodo * padre, Nodo * hijo, Nodo * vecino, bool vecino_derecho );
 		
 		/*
 		 * Cuenta en forma recursiva la cantidad de registos del arbol
 		 * cuya raiz es pasada por parametro
 		 */ 
 		unsigned int contar_regs(Nodo * nodo);
 		
 		/*
 		 * Calcula, en forma recursiva, el espacio libre que poseen
 		 * los nodos cuya raiz es pasada por param
 		 */
 		 unsigned int espacio_libre_nodos(Nodo * nodo); 
};
#endif
